#ifndef SKIPLIST_H_
#define SKIPLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXLEVEL 24             /*max level of the skip list*/
                                /*the number of the MAXLEVEL is up to the dataset*/
typedef int T;			        /*define the type of the data to be stored*/

typedef struct _Node{
	T data;
	struct _Node *next[1];      /*next[i] point to the next node in level i*/
}Node;

typedef struct _skiplist{
	int levelnum;			    /*current level number of the skip list*/
	int num[MAXLEVEL];          /*the number of nodes of each level*/
	Node *head;				    /*head point to a Node of max level next[]*/
}skiplist;

skiplist list;
#define END list.head

void init(){
	list.head = (Node *)malloc(sizeof(Node) + (MAXLEVEL-1)*sizeof(Node*));
	int i;
	for(i=0; i<MAXLEVEL; i++){
		list.head->next[i] = END;
		list.num[i] = 0;
	}
	list.levelnum = -1;
}

int find(T data){
	Node *x = list.head;
	int i;
	for(i=list.levelnum; i>=0; i--){
		while(x->next[i]!=END && x->next[i]->data<data)
			x = x->next[i];
	}
	if(x->next[0]!=END && x->next[0]->data==data)
		return 1;
	return 0;
}

Node *insert(T data){
	Node *x = list.head;
	Node *pre[MAXLEVEL];
	int i;
	for(i=list.levelnum; i>=0; i--){                  /*find the position to insert*/
		while(x->next[i]!=END && x->next[i]->data<data)
			x = x->next[i];
		pre[i] = x;                                   /*record the pre-insert position of each level*/ 
	}
	if(x->next[0]!=END && x->next[0]->data==data)
		return x->next[0];

	int insertLevel =0;								  /*generate a random insert level*/
	//while(rand()%2==1 && ++insertLevel<MAXLEVEL-1); /*rand()%2 ==1, the insertlevel can never reach 16,why??*/
													 
	while(rand()<RAND_MAX/2 && ++insertLevel<MAXLEVEL-1);
	
	if(insertLevel > list.levelnum){
		for(i=insertLevel; i>list.levelnum; i--){
			pre[i] = END;
		}
		list.levelnum = insertLevel;
	}

	Node *newNode = (Node *)malloc(sizeof(Node) + (insertLevel)*sizeof(Node *));
	newNode->data = data;
	
	for(i=insertLevel; i>=0; i--){
		newNode->next[i] = pre[i]->next[i];
		pre[i]->next[i] = newNode;

		list.num[i]++;	
	}
	
	return newNode;
}

void remove(T data){
	Node *x = list.head;
	Node *pre[MAXLEVEL];
	int i;
	for(i=list.levelnum; i>=0; i--){               /*find the position to delete*/
		while(x->next[i]!=END && x->next[i]->data<data)
			x = x->next[i];
		pre[i] = x;                                /*record the pre-insert position of each level*/ 
	}
	if(x->next[0]==END || x->next[0]->data!=data)
		return;
	x = x->next[0];									/*WOW...Wow...!!!!!, x->next[0] should be stored in x, otherwile 
													 x->next[0] will be modified by pre[]*/
	for(i=0; i<=list.levelnum; i++){
		if(pre[i]->next[i] != x)
			break;
		pre[i]->next[i] = x->next[i];
		list.num[i]--;
	}
	free(x);

	for(i=list.levelnum; i>=0; i--){              /*update the levelnum, discard the empty level*/
		if(list.head->next[i]!=END)
			break;
		list.levelnum--;
	}
	
}


void printlist(){
	int i;
	for(i=list.levelnum; i>=0; i--){
		Node *x = list.head;
		printf("%d  Head--->",i);
		while(x->next[i] != END){
			printf("%d---->",x->next[i]->data);
			x = x->next[i];
		}
		printf("End\n\n");
	}
}
void printOneLevel(int level){
	if(level > list.levelnum){
		printf("level is valid(larger than the current level of the list\n");
		return;
	}
	Node *x = list.head;
	printf("%d  Head--->",level);
	while(x->next[level] != END){
		printf("%d---->",x->next[level]->data);
		x = x->next[level];
	}
	printf("End\n\n");
}

#endif